package com.example.algorithm.dynamicprogramming;

/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 *  示例 1：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组[4,-1,2,1] 的和最大，为6 。
 *
 *  示例 2：
 * 输入：nums = [1]
 * 输出：1
 *
 *  示例 3：
 * 输入：nums = [0]
 * 输出：0
 */
public class Leetcode53_MaxSubArray {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(new Solution().maxSubArray(nums));

    }

    static class Solution {
        /**
         * 一趟遍历，使用两个变量分别存放当前最大值 和当前累加值
         * 动态规划演变而来(节省了空间)
         * @param nums
         * @return
         */
        public static int maxSubArray2(int[] nums) {
            int curSum = 0, curMaxSum = nums[0];
            for (int x : nums) {
                curSum = Math.max(curSum + x, x);//加x后变小，则累加值重置为x
                curMaxSum = Math.max(curMaxSum, curSum);//判断当前累加值和 当前最大值哪个大
            }
            return curMaxSum;
        }
        /**
         * 动态规划
         * 1.子问题:
         *   前i个元素的最大连续子序列和是多少
         *
         * 2.状态:
         *   dp(i)表示前i个元素的最大连续子序列和
         *
         * 3.状态转移方程:
         *   当 dp(i - 1) + nums[i] > nums[i]时 dp(i) = dp(i - 1) + nums[i]
         *   否则dp(i) = nums[i]
         *   目标值:max(dp(i))
         *
         * 4.边界值:
         *   dp(0) = nums[0]
         *
         * @param nums
         * @return
         */
        public int maxSubArray(int[] nums) {
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            for (int i = 1; i < dp.length; i++) {
                dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            }
            int res = Integer.MIN_VALUE;
            for (int i = 0; i < dp.length; i++) {
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }
}
